package Class034_DataStructureDesign;

import Class026.Hash;

import java.util.*;

//数据结构设计题
public class DSDesignQuestions {
    public static void main(String[] args) {
        SetAllHashMap setAllHashMap = new SetAllHashMap();
        LRUCache lruCache = new LRUCache(2);
        RandomizedSet randomizedSet = new RandomizedSet();
        AllOne allOne = new AllOne();
        allOne.inc("a");
        allOne.inc("b");
        allOne.inc("b");
        allOne.inc("c");
        allOne.inc("c");
        allOne.inc("c");
        allOne.dec("b");
        allOne.dec("b");
        //a:1, b:0, c:3
        System.out.println(allOne.getMinKey());
        allOne.dec("a");
        //a:0, b:0, c:3
        System.out.println(allOne.getMaxKey());
        System.out.println(allOne.getMinKey());
    }

    //HashMap的setAll方法
    //我们知道，get, put都是O(1)的时间复杂度
    //现在需要设计一个方法setAll, 效果是把所有的key对应的value设置为一个另一个value
    //要求也是O(1), 不能遍历
    //加上时间戳的技术，加上三个变量
    //int cnt, 表示时间戳。每条记录插入的时候，都对应一个时间戳
    //int setAllTime, 表示setAll这个操作发生的时间节点。
    //int setAllValue, 表示这个操作设置的新value
    //这个非常妙，到时候get某个value的时候，去查看它的时间戳。所有 <= 这个时间节点的，都应该是setAllValue
    //这样一来不用再遍历。
    //这样的时间戳技术类似于MySQL当中的视图
    public static class SetAllHashMap {
        public HashMap<Integer, int[]> map;
        public int cnt;
        public int setAllValue;
        public int setAllTime;

        public SetAllHashMap() {
            map = new HashMap<>();
        }

        public void put(int k, int v) {
            if (map.containsKey(k)) {
                int[] r = map.get(k);
                r[0] = v;
                r[1] = ++cnt;
            } else {
                map.put(k, new int[]{v, ++cnt});
            }
        }

        public int get(int k) {
            if (!map.containsKey(k)) {
                return -114514;
            }
            int[] record = map.get(k);
            if (record[1] <= setAllTime) {
                return setAllValue;
            } else {
                return record[0];
            }
        }

        public void setAll(int v) {
            setAllTime = cnt;
            setAllValue = v;
        }
    }

    //只能缓存一定数量的记录，
    //如果有新的记录进来，必须要把最早的删除以腾出空间
    //做到: get O(1)
    //put O(1)
    //用什么模型来表示一个记录 => 双向链表的节点
    //如果想让该模型做到O(1)，必须用一个容器来存储节点的index。必须借助哈希表
    public static class LRUCache {
        LRU lru;

        public LRUCache(int capacity) {
            lru = new LRU(capacity);
        }

        public int get(int key) {
            return lru.get(key);
        }

        public void put(int key, int value) {
            lru.put(key, value);
        }

        public static class LRU {
            HashMap<Integer, DoubleLinkedListNode> record;
            DoubleLinkedList ll;
            int capacity;

            public LRU(int c) {
                capacity = c;
                record = new HashMap<>();
                ll = new DoubleLinkedList();
            }

            public int get(int key) {
                if (!record.containsKey(key)) {
                    return -1;
                } else {
                    DoubleLinkedListNode node = record.get(key);
                    int res = node.value;
                    nodeUpdated(node);
                    return res;
                }
            }

            public void put(int key, int value) {
                if (record.containsKey(key)) {
                    DoubleLinkedListNode node = record.get(key);
                    node.value = value;
                    nodeUpdated(node);
                } else {
                    if (ll.getSize() == capacity) {
                        int rm = ll.removeHead();
                        record.remove(rm);
                    }
                    DoubleLinkedListNode node = new DoubleLinkedListNode(key, value);
                    record.put(key, node);
                    ll.addTail(node);
                }
            }

            public void nodeUpdated(DoubleLinkedListNode node) {
                ll.moveToTail(node);
            }
        }

        public static class DoubleLinkedList {
            public DoubleLinkedListNode head;
            public DoubleLinkedListNode tail;
            int size;

            public void addTail(DoubleLinkedListNode node) {
                if (head == null) {
                    head = node;
                    tail = node;
                } else {
                    tail.next = node;
                    node.pre = tail;
                    tail = node;
                }
                size++;
            }

            public int getSize() {
                return size;
            }

            public int removeHead() {
                DoubleLinkedListNode h = head;
                if (head == tail) {
                    head = null;
                    tail = null;
                } else {
                    h.next.pre = null;
                    head = h.next;
                    h.next = null;
                }
                size--;
                return h.key;
            }

            public void moveToTail(DoubleLinkedListNode node) {
                if (node == tail) {
                    return;
                }
                if (node == head) {
                    node.next.pre = null;
                    head = node.next;
                } else {
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                }
                tail.next = node;
                node.pre = tail;
                node.next = null;
                tail = node;
            }
        }

        public static class DoubleLinkedListNode {
            public int key;
            public int value;
            public DoubleLinkedListNode pre;
            public DoubleLinkedListNode next;

            public DoubleLinkedListNode(int key, int val) {
                this.key = key;
                value = val;
            }
        }
    }

    //设计一个结构，要求
    //get, insert, remove, getRandom都是O(1)
    //主体结构可以用动态数组来实现。若没有getRandom, 其实这件事情非常简单
    //记录动态数组的长度，只要用Math.Random() * (size)，即可随机获取一个位置的元素
    //但是有remove，就意味着会存在空缺
    //和堆排序一样，把抽中的数，放到最后，然后size--, 当做不存在即可
    //哈希表用来记录元素在动态数组中的位置，这样remove方法也能做到O(1)了
    public static class RandomizedSet {
        public HashMap<Integer, Integer> recordMap;
        public ArrayList<Integer> records;
        public int size;

        public RandomizedSet() {
            recordMap = new HashMap<>();
            records = new ArrayList<>();
        }

        public boolean insert(int val) {
            if (recordMap.containsKey(val)) {
                return false;
            } else {
                records.add(size, val);
                recordMap.put(val, size++);
                return true;
            }
        }

        public boolean remove(int val) {
            if (!recordMap.containsKey(val)) {
                return false;
            } else {
                int index = recordMap.get(val);
                if (index == size - 1) {
                    recordMap.remove(val);
                } else {
                    records.set(index, records.get(size - 1));
                    records.set(size - 1, val);
                    recordMap.remove(val);
                    recordMap.put(records.get(index), index);
                }
                size--;
                return true;
            }
        }

        public int getRandom() {
            int index = (int) (Math.random() * size);
            return records.get(index);
        }
    }

    //还是上面那个结构，
    //但是现在可以加入重复的了
    //然后每个值应该都有它的权重
    //总体结构不变，map的v用一个list来记录。
    //remove的时候，在list中随便取一个位置，比如get(0)
    public static class RandomizedSetWithRepeated {
        private HashMap<Integer, List<Integer>> record;
        private ArrayList<Integer> indexList;

        public RandomizedSetWithRepeated() {
            record = new HashMap<>();
            indexList = new ArrayList<>();
        }

        public boolean insert(int val) {
            if (record.containsKey(val)) {
                indexList.add(val);
                List<Integer> indexes = record.get(val);
                indexes.add(indexList.size() - 1);
                return false;
            } else {
                indexList.add(val);
                record.put(val, new ArrayList<>());
                List<Integer> indexes = record.get(val);
                indexes.add(indexList.size() - 1);
                return true;
            }
        }

        public boolean remove(int val) {
            if (!record.containsKey(val)) {
                return false;
            } else {
                int lastVal = indexList.get(indexList.size() - 1);
                List<Integer> wantToRemoveIndexes = record.get(val);
                if (lastVal == val) {
                    wantToRemoveIndexes.remove(wantToRemoveIndexes.size() - 1);
                } else {
                    List<Integer> lastValIndexes = record.get(lastVal);
                    int rmFirst = wantToRemoveIndexes.get(0);
                    //rmFirst <=> indexList.size() - 1
                    lastValIndexes.remove(lastValIndexes.size() - 1);
                    lastValIndexes.add(rmFirst);
                    wantToRemoveIndexes.remove(0);
                    indexList.set(rmFirst, lastVal);
                }

                indexList.remove(indexList.size() - 1);
                if (wantToRemoveIndexes.isEmpty()) {
                    record.remove(val);
                }
                return true;
            }
        }

        public int getRandom() {
            int rdIndex = (int) (Math.random() * indexList.size());
            return indexList.get(rdIndex);
        }
    }

    //快速获得中位数的数据结构
    public static class MedianFinder {
        PriorityQueue<Integer> bigHeap;
        PriorityQueue<Integer> smallHeap;

        public MedianFinder() {
            bigHeap = new PriorityQueue<>((a, b) -> b - a);
            smallHeap = new PriorityQueue<>();
        }

        public void addNum(int num) {
            if (bigHeap.isEmpty() || num <= bigHeap.peek()) {
                bigHeap.offer(num);
            } else {
                smallHeap.offer(num);
            }
            balance();
        }

        public double findMedium() {
            int bigSize = bigHeap.size();
            int smallSize = smallHeap.size();
            if ((bigSize + smallSize) % 2 == 0) {
                return (double) (bigHeap.poll() + smallHeap.poll());
            } else {
                if (bigSize > smallSize) {
                    return (double) (bigHeap.poll());
                } else {
                    return (double) (smallHeap.poll());
                }
            }
        }

        private void balance() {
            if (bigHeap.size() - smallHeap.size() == 2) {
                smallHeap.offer(bigHeap.poll());
            } else if (smallHeap.size() - bigHeap.size() == 2) {
                bigHeap.offer(smallHeap.poll());
            }
        }
    }

    // Design a data structure which is similar to heap/stack
    // that allow element to be pushed into it.
    // push(int val): push an integer into the top
    // int pop(): delete and return the element which frequency is the highest.
    //            if there is more than one element, remove the element in top.

    //思路:
    //核心结构是一张map记录所有词频对应的记录，因为是按先来后到的顺序弹出，所以value是链表结构
    public static class FreqStack {
        private int maxFreq;
        private final HashMap<Integer, List<Integer>> maxFreqMap = new HashMap<>();
        private final HashMap<Integer, Integer> freqMap = new HashMap<>();

        //        public FreqStack() {
//            maxFreqMap = new HashMap<>();
//            freqMap = new HashMap<>();
//        }
        public void push(int val) {
            freqMap.put(val, freqMap.getOrDefault(val, 0) + 1);
            int curFreq = freqMap.get(val);
            maxFreq = Math.max(maxFreq, curFreq);
            if (!maxFreqMap.containsKey(curFreq)) {
                maxFreqMap.put(curFreq, new ArrayList<>());
            }
            List<Integer> curFreqList = maxFreqMap.get(curFreq);
            curFreqList.add(val);
        }

        public int pop() {
            List<Integer> mfElements = maxFreqMap.get(maxFreq);
            int mfSize = mfElements.size();
            int res = mfElements.get(mfSize - 1);
            if (mfSize == 1) {
                maxFreqMap.remove(maxFreq--);
            } else {
                mfElements.remove(mfSize - 1);
            }
            freqMap.put(res, freqMap.get(res) - 1);
            if (freqMap.get(res) == 0) {
                freqMap.remove(res);
            }
            return res;
        }
    }

    // Design a data structure to store the strings' count with the ability to
    // return the strings with minimum and maximum counts.
    // Note that each function must run in O(1) average time complexity.
    public static class AllOne {
        private static final BucketLinkedList bucketLinkedList = new BucketLinkedList();
        public AllOne() {
        }
        public void inc(String key) {
            bucketLinkedList.addStr(key);
        }
        public void dec(String key) {
            bucketLinkedList.rmStr(key);
        }
        public String getMaxKey() {
            Bucket maxBucket = bucketLinkedList.getMaxFreqBucket();
            return maxBucket == null ? "" : maxBucket.getStr();
        }
        public String getMinKey() {
            Bucket minBucket = bucketLinkedList.getMinFreqBucket();
            return minBucket == null ? "" : minBucket.getStr();
        }
        public static class BucketLinkedList {
            private final Bucket head = new Bucket(0);
            private final Bucket tail = new Bucket(Integer.MAX_VALUE);
            private final HashMap<String, Bucket> bucketMap = new HashMap<>();
            public BucketLinkedList() {
                head.next = tail;
                tail.pre = head;
                bucketMap.put("head", head);
                bucketMap.put("tail", tail);
            }

            // Increments the count of the string key by 1.
            // If key does not exist in the data structure, insert it with count 1.
            public void addStr(String str) {
                if (!bucketMap.containsKey(str)) {
                    if (head.next.curFreq != 1) {
                        addBucket(str, 1, head.next);
                    } else {
                        head.next.addStrToBucket(str);
                        bucketMap.put(str, head.next);
                    }
                } else {
                    Bucket curBucket = bucketMap.get(str);
                    int f = curBucket.curFreq;
                    Bucket originalNext = curBucket.next;
                    if (originalNext.curFreq != f + 1) {
                        addBucket(str, f + 1, originalNext);
                    } else {
                        originalNext.addStrToBucket(str);
                        bucketMap.put(str, originalNext);
                    }
                    curBucket.rmStrFromBucket(str);
                    if (curBucket.getBucketSize() == 0) {
                        delBucket(curBucket, str);
                    }
                }
            }

            // Decrements the count of the string key by 1.
            // If the count of key is 0 after the decrement,
            // remove it from the data structure.
            // It is guaranteed that key exists in the data structure before the decrement.
            public void rmStr(String str) {
                assert bucketMap.containsKey(str);
                Bucket curBucket = bucketMap.get(str);
                int curFreq = curBucket.curFreq;
                curBucket.rmStrFromBucket(str);
                //第一种:当前的freq已经是1了，再删除这个str，相当于直接抹除
                //不是1，也分两种:
                //freq - 1存在和不存在。
                //存在，直接放进去，然后改bucketMap的记录
                //不存在，就新建一个freq - 1的桶，然后改bucketMap记录
                //最后，看一看curBucket的size是不是0，如果是就删除bucket
                if (curFreq == 1) {
                    bucketMap.remove(str);
                } else {
                    Bucket originalPre = curBucket.pre;
                    if (originalPre.curFreq == curFreq - 1) {
                        originalPre.addStrToBucket(str);
                        bucketMap.put(str, originalPre);
                    } else {
                        addBucket(str, curFreq - 1, curBucket);
                    }
                }
                if (curBucket.getBucketSize() == 0) {
                    delBucket(curBucket, str);
                }
            }
            /**
             * add a new bucket into the double linkedList
             *
             * @param newStr       new string in the new bucket
             * @param newFreq      the frequency of this new added string
             * @param originBucket the bucket that will be replaced by new bucket
             */
            private void addBucket(String newStr, int newFreq, Bucket originBucket) {
                Bucket newBucket = new Bucket(newFreq);
                newBucket.addStrToBucket(newStr);

                Bucket originalPre = originBucket.pre;
                newBucket.next = originBucket;
                originBucket.pre = newBucket;
                newBucket.pre = originalPre;
                originalPre.next = newBucket;

                bucketMap.put(newStr, newBucket);
            }
            /**
             * delete a bucket from the double linkedList
             *
             * @param str With pre judgement, the str is the last string in the bucket
             *            so this bucket should be removed if the str is removed
             */
            private void delBucket(Bucket bucket, String str) {
                bucket.pre.next = bucket.next;
                bucket.next.pre = bucket.pre;
            }

            // Returns one of the keys with the maximal count.
            // If no element exists, return an empty string "".
            public Bucket getMaxFreqBucket() {
                return head.next == tail ? null : tail.pre;
            }

            // Returns one of the keys with the minimum count.
            // If no element exists, return an empty string "".
            public Bucket getMinFreqBucket() {
                return head.next == tail ? null : head.next;
            }
        }

        public static class Bucket {
            public Bucket pre;
            public Bucket next;
            private int curFreq;
            private final HashSet<String> curFreqStrs = new HashSet<>();
            public Bucket(int freq) {
                pre = null;
                next = null;
                curFreq = freq;
            }
            public void addStrToBucket(String str) {
                curFreqStrs.add(str);
            }
            public void rmStrFromBucket(String str) {
                curFreqStrs.remove(str);
            }
            public int getBucketSize() {
                return curFreqStrs.size();
            }
            public String getStr() {
                return curFreqStrs.iterator().next();
            }
        }
    }
}
